package xyz.robinbingo.leetcode.a20.b05.c26;

import java.util.stream.IntStream;

public class Solution {
    public int findDuplicate(int[] nums) {
        int result = Integer.MIN_VALUE;
        int m = nums.length;
        int left = 1, right = m - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = (int) IntStream.range(0, m).filter(i -> nums[i] <= mid).count();
            if (count <= mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
                result = mid;
            }
        }
        return result;
    }
}